package com.lft.graph01.create_graph;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 无向图的实现——邻接矩阵
 */
public class GraphAdjacencyMatrix<E> implements GraphInterface<E> {
	/**
	 * 存储图的顶点的一维数组
	 */
	private E[] vertexs;
	
	/**
	 * 存储图的边的二维数组
	 */
	private int[][] edges;
	
	/**
	 * 顶点的实际数量
	 */
	private int numOfVertexs;
	
	/**
	 * 顶点的最大数量
	 */
	private int maxNumOfVertexs;
	
	/**
	 * 判断顶点是否被反问过。 true：访问过；false：未访问过。
	 */
	private boolean[] visited;
	
	/**
	 * 构造器，初始化顶点数组和边数组。
	 * @param maxNumOfVertexs
	 * @param type
	 */
	public GraphAdjacencyMatrix(int maxNumOfVertexs, Class<E> type) {
		this.maxNumOfVertexs = maxNumOfVertexs;
		edges = new int[maxNumOfVertexs][maxNumOfVertexs];
		vertexs = (E[]) Array.newInstance(type, maxNumOfVertexs);
	}
	
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	@Override
	public int getNumOfVertex() {
		return numOfVertexs;
	}
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean insertVertex(E v) {
		if (numOfVertexs >= maxNumOfVertexs) {
			return false;
		}
		vertexs[numOfVertexs++] = v;
		return true;
	}
	
	/**
	 * 删除顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean deleteVertex(E v) {
		// 遍历每个顶点
		for (int i = 0; i < numOfVertexs; i++) {
			// 当前顶点跟要删除的顶点相等。
			if (vertexs[i].equals(v)) {
				// 遍历将当前顶点用后面的顶点替换删除。
				for (int j = i; j < numOfVertexs - 1; j++) {
					// 遍历顶点数组，将后面的往前移动，替换掉要删除的顶点。
					vertexs[j] = vertexs[j + 1];
				}
				// 将数组末尾置空。
				vertexs[numOfVertexs - 1] = null;
				// 遍历列，修改边
				for (int col = i; col < numOfVertexs - 1; col++) {
					for (int row = 0; row < numOfVertexs; row++) {
						edges[col][row] = edges[col + 1][row];
					}
				}
				// 遍历行，修改边
				for (int row = i; row < numOfVertexs - 1; row++) {
					for (int col = 0; col < numOfVertexs; col++) {
						edges[col][row] = edges[col][row + 1];
					}
				}
				// 顶点数量减1
				numOfVertexs--;
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	@Override
	public int indexOfVertex(E v) {
		for (int i = 0; i < numOfVertexs; i++) {
			if (vertexs[i].equals(v)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 查找指定位置的顶点的值
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public E valueOfVertex(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex >= numOfVertexs) {
			return null;
		}
		return vertexs[vertexIndex];
	}
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return 插入成功返回 true;
	 */
	@Override
	public boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = weight;
		edges[vertexIndex2][vertexIndex1] = weight;
		return true;
	}
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 删除成功 返回true.
	 */
	@Override
	public boolean deleteEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		edges[vertexIndex1][vertexIndex2] = 0;
		edges[vertexIndex2][vertexIndex1] = 0;
		return true;
	}
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return 权值
	 */
	@Override
	public int getEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		return edges[vertexIndex1][vertexIndex2];
	}
}
